import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/15 9:15
 * @description
 */
public class FormalSolution {
    public static void main(String[] args) {
        FormalSolution solution = new FormalSolution();
        int[] nums = {3,2,1,5};
        solution.countMaxOrSubsets(nums);
    }
    int[] nums;
    int maxOr, cnt;

    public int countMaxOrSubsets(int[] nums) {
        this.nums = nums;
        this.maxOr = 0;
        this.cnt = 0;
        dfs(0, 0);
        return cnt;
    }

    public void dfs(int pos, int orVal) {
        if (pos == nums.length) {
            if (orVal > maxOr) {
                maxOr = orVal;
                cnt = 1;
            } else if (orVal == maxOr) {
                cnt++;
            }
            return;
        }
        // 选取nums[pos]
        dfs(pos + 1, orVal | nums[pos]);
        dfs(pos + 1, orVal);
    }
}
